package LeetCode;

public class LC {
//    public ListNode reverseList(ListNode head) {

        //leetcode
//        ListNode prev = head;
//        int size = 0;
//        while(prev.next != null){
//            prev = prev.next;
//            size++;
//        }
//        ListNode cur = head;
//        for (int i = 0; i < size + 1; i++) {
//            cur = cur.next;
//        }
//        return cur;

//        leetcode82
//        ListNode dummyHead = new ListNode(101);
//        ListNode prev = dummyHead;
//        ListNode cur = head;
//        dummyHead.next = head;
//        while(cur != null){
//            ListNode next = cur.next;
//            if(next == null){
//                return dummyHead.next;
//            }
//            if(cur.val == next.val){
//                while(next != null && cur.val == next.val){
//                    next = next.next;
//                }
//                prev = next;
//                cur = next;
//            }else{
//                cur = cur.next;
//                next = next.next;
//                prev = prev.next;
//            }
//        }
//
//        return dummyHead.next;

//        leetcode206
//        ListNode prev = null;
//        ListNode cur = head;
//        while(cur != null){
//            ListNode next = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = next;
//        }
//        return prev;
//    }
//
//    LeetCode21
//public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//    ListNode dummyHead = new ListNode(101);
//    ListNode last = dummyHead;
//    while(list1 != null && list2 != null){
//        if(list1.val <= list2.val){
//            last.next = list1;
//            last = list1;
//            list1 = list1.next;
//        }else{
//            last.next = list2;
//            last = list2;
//            list2 = list2.next;
//        }
//    }
//    if(list1 == null){
//        last.next = list2;
//    }else{
//        last.next = list1;
//    }
//    return dummyHead.next;
//    递归
//    if(list1 == null){
//        return list2;
//    }
//    if(list2 == null){
//        return list1;
//    }
//    if(list1.val <= list2.val){
//        list1.next =  mergeTwoLists(list1.next,list2);
//        return list1;
//    }else{
//        list2.next =  mergeTwoLists(list2.next,list1);
//        return list2;
//    }
//}
//    leetcode 160
//    ListNode pa = headA;
//    ListNode pb = headB;
//        while(pa != pb){
//        if(pa != null){
//            pa = pa.next;
//        }else{
//            pa = headB;
//        }
//        if(pb != null){
//            pb = pb.next;
//        }else{
//            pb = headA;
//        }
//    }
//        if(pa == null){
//        return null;
//    }else{
//        return pa;
//    }
//
//    LeetCode142
//    ListNode fast = head;
//    ListNode low = head;
//        while(fast != null && fast.next != null){
//        fast = fast.next.next;
//        low = low.next;
//        if(fast == low){
//            ListNode third = head;
//            while(third != low){
//                third = third.next;
//                low = low.next;
//            }
//            return low;
//        }
//    }
//        return null;
//   LeetCode 27
//    public boolean isPalindrome(ListNode head) {
//        List<Integer> vals = new ArrayList<Integer>();
//
//        // 将链表的值复制到数组中
//        ListNode currentNode = head;
//        while (currentNode != null) {
//            vals.add(currentNode.val);
//            currentNode = currentNode.next;
//        }
//
//        // 使用双指针判断是否回文
//        int front = 0;
//        int back = vals.size() - 1;
//        while (front < back) {
//            if (!vals.get(front).equals(vals.get(back))) {
//                return false;
//            }
//            front++;
//            back--;
//        }
//        return true;
//    }

//    LeetCode  27 递归
//private ListNode frontPointer;

//    private boolean recursivelyCheck(ListNode currentNode) {
//        if (currentNode != null) {
//            if (!recursivelyCheck(currentNode.next)) {
//                return false;
//            }
//            if (currentNode.val != frontPointer.val) {
//                return false;
//            }
//            frontPointer = frontPointer.next;
//        }
//        return true;
//    }
//
//    public boolean isPalindrome(ListNode head) {
//        frontPointer = head;
//        return recursivelyCheck(head);
//    }

//    leetCode24
//    ListNode prev = null;
//    ListNode curr = head;
//        while (curr != null) {
//        ListNode next = curr.next;
//        curr.next = prev;
//        prev = curr;
//        curr = next;
//    }
//
//    LeetCode24递归
//    if (head == null || head.next == null) {
//        return head;
//    }
//    ListNode newHead = reverseList(head.next);
//    head.next.next = head;
//    head.next = null;
//        return newHead;
//class Solution {
//    public void reorderList(ListNode head) {
//        if (head == null) {
//            return;
//        }
//        List<ListNode> list = new ArrayList<ListNode>();
//        ListNode node = head;
//        while (node != null) {
//            list.add(node);
//            node = node.next;
//        }
//        int i = 0, j = list.size() - 1;
//        while (i < j) {
//            list.get(i).next = list.get(j);
//            i++;
//            if (i == j) {
//                break;
//            }
//            list.get(j).next = list.get(i);
//            j--;
//        }
//        list.get(i).next = null;
//    }
//}
//    029
//class Solution {
//    public Node insert(Node head, int insertVal) {
//        if(head==null){
//            Node node=new Node(insertVal);
//            node.next=node;
//            return node;
//        }
//        Node max=head,min=head;
//        Node p=head.next;
//        while (p!=head){
//            if(p.val>max.val)max=p;
//            if(p.val<min.val)min=p;
//            p=p.next;
//        }
//        if(max==min){
//            max.next=new Node(insertVal,max.next);
//        }
//        else if(insertVal>=max.val||insertVal<=min.val){
//            while (max.next.val==max.val)max=max.next;
//            max.next=new Node(insertVal,max.next);
//        }else{
//            while (min.next.val<insertVal)min=min.next;
//            min.next=new Node(insertVal,min.next);
//        }
//        return head;
//    }
//}
//    力扣23
//public ListNode mergeTwoLists(ListNode a, ListNode b) {
//    if (a == null || b == null) {
//        return a != null ? a : b;
//    }
//    ListNode head = new ListNode(0);
//    ListNode tail = head, aPtr = a, bPtr = b;
//    while (aPtr != null && bPtr != null) {
//        if (aPtr.val < bPtr.val) {
//            tail.next = aPtr;
//            aPtr = aPtr.next;
//        } else {
//            tail.next = bPtr;
//            bPtr = bPtr.next;
//        }
//        tail = tail.next;
//    }
//    tail.next = (aPtr != null ? aPtr : bPtr);
//    return head.next;
//}
//
//public class Solution {
//    public ListNode detectCycle(ListNode head) {
//        ListNode pos = head;
//        Set<ListNode> visited = new HashSet<ListNode>();
//        while (pos != null) {
//            if (visited.contains(pos)) {
//                return pos;
//            } else {
//                visited.add(pos);
//            }
//            pos = pos.next;
//        }
//        return null;
//    }
//}
//class Solution {
//    public Node insert(Node head, int insertVal) {
//        if(head==null){
//            Node node=new Node(insertVal);
//            node.next=node;
//            return node;
//        }
//        Node max=head,min=head;
//        Node p=head.next;
//        while (p!=head){
//            if(p.val>max.val)max=p;
//            if(p.val<min.val)min=p;
//            p=p.next;
//        }
//        if(max==min){
//            max.next=new Node(insertVal,max.next);
//        }
//        else if(insertVal>=max.val||insertVal<=min.val){
//            while (max.next.val==max.val)max=max.next;
//            max.next=new Node(insertVal,max.next);
//        }else{
//            while (min.next.val<insertVal)min=min.next;
//            min.next=new Node(insertVal,min.next);
//        }
//        return head;
//    }
//}
//class Solution {
//    public ListNode oddEvenList(ListNode head) {
//        if (head == null) {
//            return head;
//        }
//        ListNode evenHead = head.next;
//        ListNode odd = head, even = evenHead;
//        while (even != null && even.next != null) {
//            odd.next = even.next;
//            odd = odd.next;
//            even.next = odd.next;
//            even = even.next;
//        }
//        odd.next = evenHead;
//        return head;
//    }
//}
//class Solution {
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        // 设置两个栈，将两个链表分别入栈
//        Deque<Integer> stack1 = new ArrayDeque<>();
//        Deque<Integer> stack2 = new ArrayDeque<>();
//
//        while (l1 != null) {
//            stack1.push(l1.val);
//            l1 = l1.next;
//        }
//        while (l2 != null){
//            stack2.push(l2.val);
//            l2 = l2.next;
//        }
//
//        // ans 保存相加后的链表头
//        ListNode ans = null;
//        // bit 保存进位值
//        int bit = 0;
//        // 将两个栈中的数据同时出栈，可以达到右端对齐的效果
//        while (!stack1.isEmpty() || !stack2.isEmpty()){
//            int sum = 0;
//            if(stack1.isEmpty()){
//                sum += stack2.pop();
//            }else if(stack2.isEmpty()){
//                sum += stack1.pop();
//            }else {
//                sum += (stack1.pop() + stack2.pop());
//            }
//            // 更新相加后的值，以及进位值
//            sum += bit;
//            bit = sum / 10;
//            sum %= 10;
//            // 将相加后的值，作为一个节点插入
//            ListNode node = new ListNode(sum);
//            node.next = ans;
//            ans = node;
//        }
//        // 注意：最有一次相加可能存在进位，需要进行判断，是否需要再创建一个新的节点
//        if(bit > 0){
//            ListNode node = new ListNode(bit);
//            node.next = ans;
//            ans = node;
//        }
//        // 返回结果
//        return ans;
//    }
//}
//    class Solution {
//        static final int kMod1 = 1000000007;
//        static final int kMod2 = 1337;
//
//        public int repeatedStringMatch(String a, String b) {
//            int an = a.length(), bn = b.length();
//            int index = strStr(a, b);
//            if (index == -1) {
//                return -1;
//            }
//            if (an - index >= bn) {
//                return 1;
//            }
//            return (bn + index - an - 1) / an + 2;
//        }
//
//        public int strStr(String haystack, String needle) {
//            int n = haystack.length(), m = needle.length();
//            if (m == 0) {
//                return 0;
//            }
//
//            int k1 = 1000000009;
//            int k2 = 1337;
//            Random random = new Random();
//            int kMod1 = random.nextInt(k1) + k1;
//            int kMod2 = random.nextInt(k2) + k2;
//
//            long hashNeedle = 0;
//            for (int i = 0; i < m; i++) {
//                char c = needle.charAt(i);
//                hashNeedle = (hashNeedle * kMod2 + c) % kMod1;
//            }
//            long hashHaystack = 0, extra = 1;
//            for (int i = 0; i < m - 1; i++) {
//                hashHaystack = (hashHaystack * kMod2 + haystack.charAt(i % n)) % kMod1;
//                extra = (extra * kMod2) % kMod1;
//            }
//            for (int i = m - 1; (i - m + 1) < n; i++) {
//                hashHaystack = (hashHaystack * kMod2 + haystack.charAt(i % n)) % kMod1;
//                if (hashHaystack == hashNeedle) {
//                    return i - m + 1;
//                }
//                hashHaystack = (hashHaystack - extra * haystack.charAt((i - m + 1) % n)) % kMod1;
//                hashHaystack = (hashHaystack + kMod1) % kMod1;
//            }
//            return -1;
//        }
//    }
//class Solution {
//    public ListNode swapNodes(ListNode head, int k) {
//        ListNode left = head;// 第k个节点
//        ListNode right = head;// 倒数第k个节点
//        for(int i = 1; i < k; i++){left = left.next;}
//        ListNode cur = left;
//        while(cur.next != null){
//            right = right.next;
//            cur = cur.next;
//        }
//        // 交换左右两个节点的值
//        int m = right.val;
//        right.val = left.val;
//        left.val = m;
//        return head;
//    }
//}


//    class Solution {
//        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//            int i=0;
//            ListNode ans = new ListNode(0);
//            ListNode node = ans;
//            while(l1 != null || l2 != null){
//                int sum = 0;
//                if(l1 != null){
//                    sum += l1.val;
//                    l1 = l1.next;
//                }
//                if(l2 != null){
//                    sum += l2.val;
//                    l2 = l2.next;
//                }
//                sum += i;
//                i = sum / 10;
//                node.next = new ListNode(sum % 10);
//                node = node.next;
//            }
//            if(i>0){
//                node.next = new ListNode(i);
//            }
//            return ans.next;
//        }
//    }
//class Solution {
//    public int longestStrChain(String[] words) {
//        HashMap<Integer, List<String>> hashMap = new HashMap<>();
//
//        int minLength = 1000;
//        int maxLength = 0;
//        for (String word : words) {
//            minLength = Math.min(minLength,word.length());
//            maxLength = Math.max(maxLength,word.length());
//            if (!hashMap.containsKey(word.length())){
//                hashMap.put(word.length(),new ArrayList<>());
//            }
//            hashMap.get(word.length()).add(word);
//        }
//        int res = 1;
//        for (int currentLength = minLength; res+currentLength <= maxLength; currentLength++) {
//            int l = currentLength;
//            int chainL = 1;
//            List<String> stringList = hashMap.get(l);
//            HashSet<String> nextStrings = new HashSet<>();
//            l++;
//
//            while (hashMap.containsKey(l)){
//                List<String> nextList = hashMap.get(l);
//                for (String str1 : stringList) {
//                    for (String str2 : nextList) {
//                        if (isBefore(str1,str2)){
//                            nextStrings.add(str2);
//                        }
//                    }
//                }
//                if (nextStrings.size()>0){
//                    chainL++;
//                }else{
//                    break;
//                }
//                l++;
//                stringList = new ArrayList<>(nextStrings);
//                nextStrings.clear();
//            }
//            res = Math.max(chainL,res);
//        }
//
//        return res;
//    }
//
//    /**
//     * 双指针
//     */
//    private boolean isBefore(String str1, String str2){
//        int idx1 = 0;
//        int idx2 = 0;
//        //头对齐
//        if (str1.charAt(0)!= str2.charAt(0)){
//            idx2 = 1;
//        }
//        while (idx1 < str1.length() && idx2< str2.length()){
//            while (idx2< str2.length() && str1.charAt(idx1) != str2.charAt(idx2)){
//                idx2++;
//            }
//            if (idx2< str2.length() && str1.charAt(idx1) == str2.charAt(idx2)){
//                idx2++;
//                idx1++;
//            }
//        }
//        return idx1 == str1.length();
//    }
//}

//    class Solution {
//        /**
//         * 单调栈(从前往后)
//         */
//        public int[] nextLargerNodes(ListNode head) {
//            //list存储: 当前索引下, 右边最大元素值(即答案值) 或 当前索引于链表中的元素值(最后会将该值替换为答案值)
//            List<Integer> list = new ArrayList<>();
//            Stack<Integer> stack = new Stack<>();
//            int index = 0;
//            while (head != null){
//                int ele = head.val;
//                while (!stack.isEmpty() && list.get(stack.peek()) < ele){
//                    //出栈, 替换list指定索引的值 当前索引于链表中的元素值 替换为=> 右边最大元素值(即答案值)
//                    list.set(stack.pop(), ele);
//                }
//                //索引+1, 并将链表中该元素值加到指定索引(参数index)位置中
//                stack.push(index);
//                list.add(ele);
//                index++;
//                head = head.next;
//            }
//            //将没有右边最大元素的置为0
//            while (!stack.isEmpty()){
//                list.set(stack.pop(), 0);
//            }
//            return list.stream().mapToInt(Integer::intValue).toArray();
//        }
//    表示数值的字符串
//class Solution {
//    public boolean isNumber(String s) {
//        Map<State, Map<CharType, State>> transfer = new HashMap<State, Map<CharType, State>>();
//        Map<CharType, State> initialMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_SPACE, State.STATE_INITIAL);
//            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
//            put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
//            put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
//        }};
//        transfer.put(State.STATE_INITIAL, initialMap);
//        Map<CharType, State> intSignMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
//            put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
//        }};
//        transfer.put(State.STATE_INT_SIGN, intSignMap);
//        Map<CharType, State> integerMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
//            put(CharType.CHAR_EXP, State.STATE_EXP);
//            put(CharType.CHAR_POINT, State.STATE_POINT);
//            put(CharType.CHAR_SPACE, State.STATE_END);
//        }};
//        transfer.put(State.STATE_INTEGER, integerMap);
//        Map<CharType, State> pointMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
//            put(CharType.CHAR_EXP, State.STATE_EXP);
//            put(CharType.CHAR_SPACE, State.STATE_END);
//        }};
//        transfer.put(State.STATE_POINT, pointMap);
//        Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
//        }};
//        transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);
//        Map<CharType, State> fractionMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
//            put(CharType.CHAR_EXP, State.STATE_EXP);
//            put(CharType.CHAR_SPACE, State.STATE_END);
//        }};
//        transfer.put(State.STATE_FRACTION, fractionMap);
//        Map<CharType, State> expMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
//            put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
//        }};
//        transfer.put(State.STATE_EXP, expMap);
//        Map<CharType, State> expSignMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
//        }};
//        transfer.put(State.STATE_EXP_SIGN, expSignMap);
//        Map<CharType, State> expNumberMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
//            put(CharType.CHAR_SPACE, State.STATE_END);
//        }};
//        transfer.put(State.STATE_EXP_NUMBER, expNumberMap);
//        Map<CharType, State> endMap = new HashMap<CharType, State>() {{
//            put(CharType.CHAR_SPACE, State.STATE_END);
//        }};
//        transfer.put(State.STATE_END, endMap);
//
//        int length = s.length();
//        State state = State.STATE_INITIAL;
//
//        for (int i = 0; i < length; i++) {
//            CharType type = toCharType(s.charAt(i));
//            if (!transfer.get(state).containsKey(type)) {
//                return false;
//            } else {
//                state = transfer.get(state).get(type);
//            }
//        }
//        return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END;
//    }
//
//    public CharType toCharType(char ch) {
//        if (ch >= '0' && ch <= '9') {
//            return CharType.CHAR_NUMBER;
//        } else if (ch == 'e' || ch == 'E') {
//            return CharType.CHAR_EXP;
//        } else if (ch == '.') {
//            return CharType.CHAR_POINT;
//        } else if (ch == '+' || ch == '-') {
//            return CharType.CHAR_SIGN;
//        } else if (ch == ' ') {
//            return CharType.CHAR_SPACE;
//        } else {
//            return CharType.CHAR_ILLEGAL;
//        }
//    }
//
//    enum State {
//        STATE_INITIAL,
//        STATE_INT_SIGN,
//        STATE_INTEGER,
//        STATE_POINT,
//        STATE_POINT_WITHOUT_INT,
//        STATE_FRACTION,
//        STATE_EXP,
//        STATE_EXP_SIGN,
//        STATE_EXP_NUMBER,
//        STATE_END
//    }
//
//    enum CharType {
//        CHAR_NUMBER,
//        CHAR_EXP,
//        CHAR_POINT,
//        CHAR_SIGN,
//        CHAR_SPACE,
//        CHAR_ILLEGAL
//    }
//}
////两两交换
//class Solution {
//    public ListNode swapPairs(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode newHead = head.next;
//        head.next = swapPairs(newHead.next);
//        newHead.next = head;
//        return newHead;
//    }
//}
//class Solution {
//    public ListNode removeZeroSumSublists(ListNode head) {
//        //找到头节点
//        while(true){
//            ListNode nHead = sumIsZero(head);
//            if(nHead == head){  //返回值和头节点相同，说明以head为头的链表，节点和不为0
//                head = nHead;
//                break;
//            }
//            head = nHead;
//        }
//
//        //对于后续的每一个节点，都剔除和为0的部分，
//        //将节点和不为0的开头拼接到当前节点的后面
//        ListNode node = head;
//        while(node != null){
//            ListNode next = sumIsZero(node.next);
//            if(next == node.next){
//                node = node.next;
//            }
//            else {
//                node.next = next;
//            }
//        }
//
//        return head;
//    }
//
//    //判断head为起点，连续的链表和是否==0.  如果不存在返回head,如何存在，返回此段节点后面的一个节点
//    public ListNode sumIsZero(ListNode head){
//        if(head == null){
//            return head;
//        }
//        if(head.val == 0){
//            return head.next;
//        }
//
//
//        ListNode node = head;
//        int sum = 0;
//        while(node != null){
//            sum += node.val;
//            if(sum == 0){
//                return node.next;
//            }
//            node = node.next;
//        }class Solution {
//    public ListNode reverseEvenLengthGroups(ListNode head) {
//        return reverse(head,1);
//    }
//
//    ListNode reverse(ListNode head,int group){   //group 为自然递增序列（1，2，3，4，5……）
//        if(head == null){
//            return head;
//        }
//        ListNode slow = head; //慢指针--->指向每个链表头
//        ListNode fast = head;  //快指针--->指向下一个链表头
//        ListNode middle = head;//当前链表的尾节点
//        int count = 0;   //记录当前链表的的节点个数
//        for(int i = 0;i < group;i++){
//            if(fast == null){
//                if(count < group && count % 2 != 0){
//                    ListNode tmp = reverse(fast,group + 1);
//                    return slow;
//                }else if(count < group && count % 2 == 0){
//                    ListNode newHead = reverseList(slow,fast);
//                    slow.next = reverse(fast,group + 1);
//                    return newHead;
//                }
//                return null;
//            }else{
//                count++;
//            }
//            if(i < group - 1){
//                middle = middle.next;
//            }
//
//            fast = fast.next;
//        }
//        if(group % 2 != 0){
//            ListNode tmp = reverse(fast,group + 1);
//            middle.next = tmp;
//            return slow;
//        }else{
//            ListNode newHead = reverseList(slow,fast);
//            slow.next = reverse(fast,group + 1);
//            return newHead;
//        }
//
//    }
//
//    ListNode reverseList(ListNode head,ListNode fast){
//        ListNode pre = null;
//        ListNode cur = head;
//        while(cur != fast){
//            ListNode nextL = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = nextL;
//        }
//
//        return pre;
//    }
//}
//
//
//        return head;
//    }
//}
//
//    class Solution
//    {
//        public int[] nodesBetweenCriticalPoints(ListNode head)
//        {
//            List<Integer> nums = new ArrayList<>();
//            ListNode p = head;
//            while (p != null)
//            {
//                nums.add(p.val);
//                p = p.next;
//            }
//
//            int n = nums.size();
//            List<Integer> a = new ArrayList<>();
//            for (int i = 1; i < n - 1; i ++)
//            {
//                if (nums.get(i - 1) > nums.get(i) && nums.get(i) < nums.get(i + 1)){
//                    a.add(i);
//                }
//                else if (nums.get(i - 1) < nums.get(i) && nums.get(i) > nums.get(i + 1)){
//                    a.add(i);
//                }
//            }
//
//            int an = a.size();
//            if (an < 2){
//                return new int [] {-1, -1};
//            }
//            int max_ = a.get(a.size() - 1) - a.get(0);
//            int min_ = Integer.MAX_VALUE;
//            for (int i = 1; i < an; i ++)
//            {
//                min_ = Math.min(min_, a.get(i) - a.get(i - 1));
//            }
//            return new int [] {min_, max_};
//        }
//    }
//class Solution {
//    public int findLongestChain(int[][] pairs) {
//        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
//        int N = pairs.length;
//        int[] dp = new int[N];
//        Arrays.fill(dp, 1);
//
//        for (int j = 1; j < N; ++j) {
//            for (int i = 0; i < j; ++i) {
//                if (pairs[i][1] < pairs[j][0])
//                    dp[j] = Math.max(dp[j], dp[i] + 1);
//            }
//        }
//
//        int ans = 0;
//        for (int x: dp) if (x > ans) ans = x;
//        return ans;
//    }
//}
//class Solution {
//    public ListNode reverseKGroup(ListNode head, int k) {
//        ListNode hair = new ListNode(0);
//        hair.next = head;
//        ListNode pre = hair;
//
//        while (head != null) {
//            ListNode tail = pre;
//            // 查看剩余部分长度是否大于等于 k
//            for (int i = 0; i < k; ++i) {
//                tail = tail.next;
//                if (tail == null) {
//                    return hair.next;
//                }
//            }
//            ListNode nex = tail.next;
//            ListNode[] reverse = myReverse(head, tail);
//            head = reverse[0];
//            tail = reverse[1];
//            // 把子链表重新接回原链表
//            pre.next = head;
//            tail.next = nex;
//            pre = tail;
//            head = tail.next;
//        }
//
//        return hair.next;
//    }
//
//    public ListNode[] myReverse(ListNode head, ListNode tail) {
//        ListNode prev = tail.next;
//        ListNode p = head;
//        while (prev != tail) {
//            ListNode nex = p.next;
//            p.next = prev;
//            prev = p;
//            p = nex;
//        }
//        return new ListNode[]{tail, head};
//    }
//}
//class Solution {
//
//    TreeNode minNode;
//
//    public TreeNode convertBiNode(TreeNode root) {
//        reverseInorder(root);
//        return minNode;
//    }
//
//    private void reverseInorder(TreeNode root) {
//        if (root == null) {
//            return;
//        }
//        //遍历右子树
//        reverseInorder(root.right);
//        //遍历根节点
//        root.right = minNode;
//        minNode = root;
//        //遍历左子树
//        reverseInorder(root.left);
//        //置空左指针
//        root.left = null;
//    }
//}
//class MyCalendar {
//    TreeMap<Integer, Integer> treeMap;
//    public MyCalendar() {
//        treeMap = new TreeMap<>();
//    }
//
//    public boolean book(int start, int end) {
//        Map.Entry<Integer, Integer> event = treeMap.floorEntry(start);
//        if(event != null && event.getValue() > start) return false;
//
//        event = treeMap.ceilingEntry(start);
//        if(event != null && event.getKey() < end) return false;
//
//        treeMap.put(start, end);
//
//        return true;
//    }
//}
//class Solution {
//    public void flatten(TreeNode root) {
//        List<TreeNode> list = new ArrayList<TreeNode>();
//        preorderTraversal(root, list);
//        int size = list.size();
//        for (int i = 1; i < size; i++) {
//            TreeNode prev = list.get(i - 1), curr = list.get(i);
//            prev.left = null;
//            prev.right = curr;
//        }
//    }
//
//    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
//        if (root != null) {
//            list.add(root);
//            preorderTraversal(root.left, list);
//            preorderTraversal(root.right, list);
//        }
//    }
//}
//class Solution {
//    public ListNode insertionSortList(ListNode head) {
//        if (head == null) {
//            return head;
//        }
//        ListNode dummyHead = new ListNode(0);
//        dummyHead.next = head;
//        ListNode lastSorted = head, curr = head.next;
//        while (curr != null) {
//            if (lastSorted.val <= curr.val) {
//                lastSorted = lastSorted.next;
//            } else {
//                ListNode prev = dummyHead;
//                while (prev.next.val <= curr.val) {
//                    prev = prev.next;
//                }
//                lastSorted.next = curr.next;
//                curr.next = prev.next;
//                prev.next = curr;
//            }
//            curr = lastSorted.next;
//        }
//        return dummyHead.next;
//    }
//}
//class Solution {
//    public ListNode reverseKGroup(ListNode head, int k) {
//        ListNode hair = new ListNode(0);
//        hair.next = head;
//        ListNode pre = hair;
//
//        while (head != null) {
//            ListNode tail = pre;
//            // 查看剩余部分长度是否大于等于 k
//            for (int i = 0; i < k; ++i) {
//                tail = tail.next;
//                if (tail == null) {
//                    return hair.next;
//                }
//            }
//            ListNode nex = tail.next;
//            ListNode[] reverse = myReverse(head, tail);
//            head = reverse[0];
//            tail = reverse[1];
//            // 把子链表重新接回原链表
//            pre.next = head;
//            tail.next = nex;
//            pre = tail;
//            head = tail.next;
//        }
//
//        return hair.next;
//    }
//
//    public ListNode[] myReverse(ListNode head, ListNode tail) {
//        ListNode prev = tail.next;
//        ListNode p = head;
//        while (prev != tail) {
//            ListNode nex = p.next;
//            p.next = prev;
//            prev = p;
//            p = nex;
//        }
//        return new ListNode[]{tail, head};
//    }
//}

//    class Solution {
//        Map<Node, Node> cachedNode = new HashMap<Node, Node>();
//
//        public Node copyRandomList(Node head) {
//            if (head == null) {
//                return null;
//            }
//            if (!cachedNode.containsKey(head)) {
//                Node headNew = new Node(head.val);
//                cachedNode.put(head, headNew);
//                headNew.next = copyRandomList(head.next);
//                headNew.random = copyRandomList(head.random);
//            }
//            return cachedNode.get(head);
//        }
//    }
//class Solution {
//    public ListNode rotateRight(ListNode head, int k) {
//        if (k == 0 || head == null || head.next == null) {
//            return head;
//        }
//        int n = 1;
//        ListNode iter = head;
//        while (iter.next != null) {
//            iter = iter.next;
//            n++;
//        }
//        int add = n - k % n;
//        if (add == n) {
//            return head;
//        }
//        iter.next = head;
//        while (add-- > 0) {
//            iter = iter.next;
//        }
//        ListNode ret = iter.next;
//        iter.next = null;
//        return ret;
//    }
//}
//class Solution {
//    public Node flatten(Node head) {
//        dfs(head);
//        return head;
//    }
//
//    public Node dfs(Node node) {
//        Node cur = node;
//        // 记录链表的最后一个节点
//        Node last = null;
//
//        while (cur != null) {
//            Node next = cur.next;
//            //  如果有子节点，那么首先处理子节点
//            if (cur.child != null) {
//                Node childLast = dfs(cur.child);
//
//                next = cur.next;
//                //  将 node 与 child 相连
//                cur.next = cur.child;
//                cur.child.prev = cur;
//
//                //  如果 next 不为空，就将 last 与 next 相连
//                if (next != null) {
//                    childLast.next = next;
//                    next.prev = childLast;
//                }
//
//                // 将 child 置为空
//                cur.child = null;
//                last = childLast;
//            } else {
//                last = cur;
//            }
//            cur = next;
//        }
//        return last;
//    }
//}
//class Solution {
//    public int pairSum(ListNode head) {
//
//        ListNode fast = head;
//        ListNode slow = head;
//        while(fast.next != null && fast.next.next != null){
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        ListNode oddListNode = slow.next;
//        slow.next = null;
//
//        ListNode cur = oddListNode;
//        ListNode prev = null;
//        while(cur != null){
//            ListNode next = cur.next;
//            cur.next = prev;
//            prev = cur;
//            cur = next;
//        }
//
//        int res = 0;
//
//        while(head != null){
//            res = Math.max(prev.val+head.val,res);
//            head = head.next;
//            prev = prev.next;
//        }
//        return res;
//
//    }
//}
//public ListNode mergeTwoLists(ListNode a, ListNode b) {
//    if (a == null || b == null) {
//        return a != null ? a : b;
//    }
//    ListNode head = new ListNode(0);
//    ListNode tail = head, aPtr = a, bPtr = b;
//    while (aPtr != null && bPtr != null) {
//        if (aPtr.val < bPtr.val) {
//            tail.next = aPtr;
//            aPtr = aPtr.next;
//        } else {
//            tail.next = bPtr;
//            bPtr = bPtr.next;
//        }
//        tail = tail.next;
//    }
//    tail.next = (aPtr != null ? aPtr : bPtr);
//    return head.next;
//}

}
